Local access markets in the telecommunications business are becoming increasingly competitive with the advent of deregulation. Local access service requires the provision of subscriber connectivity to the traditional Plain Old Telephone Service (POTS), a variety of data services, as well as new telecommunications services such as Cable TV, wireless, Personal Communications Service (PCS), and high bandwidth digital connectivity to access the Internet. Two of the most desirable attributes of a network designed to provide these services are reliability and the ability to grow economically to keep pace with the market.
In general, a telecommunications t=ansport network consists of a set of demand nodes from which demand originates, a set of destination nodes at which demand terminates and a set of links and intermediate nodes that join the two sets of nodes. In the particular context of a local access network, the demand nodes consist of large business premises and Local Serving Offices (LSOs). An LSO represents a collection point of demand traffic from many residential and small business customers. The destination nodes in the local network are the network nodes at which terminating cross connect equipment and local and long-distance switches are placed. A particular network node to which most of the demand is destined is designated as the Service Node.
The transport technology known as Synchronous Optical Network (SONET) possesses the attributes required by local access networks. That is, SONET provides an economical, flexible and highly reliable transport mechanism for modem telecommunications networks. In particular, SONET facilitates the design of Self-Healing Ring (SHR) netvorks, which offer rapid service restoration after a network failure, e.g., after a fiber cut. The telecommunications industry is rapidly deploying SONET ring networks in many of its networks, including local networks. One particular SONET architecture that would be appropriate for local access networks is known as Path-in-Line (PIL). A PIL architecture employs a plurality of interlocked rings arranged in a hierarchical fashion.
The design methodology for a SONET architecture may be divided into the design of the network topology and the design of the SONET rings themselves. The network topology refers to the spatial arrangement of the links in the network. For example, in a ring topology, several links are connected in a cycle to form a topological ring. The SONET rings refer to the physical communication paths that traverse the network ring topology. More specifically, a SONET ring consists of a single fiber pair that traverses each link of the topological ring. Because of limits on capacity and the number of nodes that may be supported, several SONET rings may be required to serve all the nodes on a single topological ring, Such SONET rings that traverse the same topological ring are said to be stacked.
A primary objective of a network design method is to construct the least cost network that meets certain topological constraints. The cost of a SONET network is comprised of the transport cost involved in creating links of optical fiber plus the cost of the SONET equipment at the nodes. The transport cost consists of two major components: mileage cost and fiber cost. The mileage cost depends on the actual length of network links and represents the cost of establishing these links, including the right-of-way (ROW) costs and Engineering & Implementation (E&I) costs. The fiber cost depends on both the mileage and the number of fiber strands required, which in turn depends on the demand. The equipment cost is largely a function of the SONET architecture and the demand. Given this network design objective, the problem addressed by network design may be reformulated with more particularity as follows: Given a set of demand, destination and intermediate nodes, a SONET architecture, a cost structure, and a set of topological constraints, the design method determines which links should he constructed and how much equipment should be deployed to provide the most economical connectivity among the nodes. The constraints generally dictate limits on the membership and size of the topological structures. The constraints imposed on a PIL SONET architecture appropriate for local access include a dual hubbed hierarchical ring topology with all the destination nodes residing on the backbone ring so that traffic is directed from a large number of demand nodes to a relatively few destination nodes.
Most of the demand nodes lie on topological rings. Some demand nodes, however, may be connected to a node on the ring network, known as a "root" node, via a hub and spoke topology. A hub and spoke topology resembles a tree, consisting of links, known as spokes, that interconnect a set of demand nodes without forming a cycle. The stacked SONET rings associated with the toplogical ring on which a hub & spoke network is "rooted" also serve the demand nodes on the hub & spoke network.
Known methodologies for designing SONET networks have focused on the use of bi-directional line switched SONET rings for core networks. Such networks, which are well suited for situations where significant point-to point demand exists, include the long distance core network and the network serving the local exchange carriers' switch-to-switch traffic. BellCore's SONET Toolkit for example, offers such design algorithms. (See Cosares, S. et al., "SONET Toolkit: A Decision Support System for Design of Robust and Cost-Effective Fiber-Optic Networks", Interfaces, 25 (1995) pp. 20-40, as well as Wasem, O. J., "An Algorithm for Designing Rings for Survivable Fiber Networks", IEEE Transactions on Reliability, 40 (1991) pp. 428-432, Wasem, O. J, et al. "Survivable SONET Networks--Design Methodology", IEEE Journal on Selected Areas in Communications, 12 (1994) pp. 205-212 and Wu, T. et al., "A Multi-period Design Model for Survivable Network Architecture Selection for SONET Interoffice Networks" IEEE Transactions on Reliability, 40 (1991) pp. 417-427). Another method and system for ring design in such networks was developed by US West; see Cox, L. A. et al., "Method and System for Planning and Installing Communications Networks", U.S. Pat. No. 5,515,367, May 7, 1996. Laguna, M., "Clustering for the Design of SONET Rings in Interoffice Telecommunications", Management Science, 40 (1994) pp. 1533-1541 considers clustering in a non-hierarchical ring network with significant point-to point demand. Altinkemer, K., "Topological Design of Ring Networks" Computers and Operations Research, 21 (1994) pp. 421-431 discloses a method for designing access rings when the backbone ring has already been determined and only a single hub per access ring is required. Similarly, Shi, J. and Fonseka, J. P., "Hierarchical Self-Healing Rings", IEEE/ACM Transactions on Networking, 3 (1995) pp. 690-697 address the problem of designing a hierarchical network with a single hub per access ring and a uniform number of nodes per ring.
The known methodologies do not address the problem of designing a SONET architecture appropriate for local access on which are imposed the previously enumerated topological constraints. In particular, the known methodologies do not address the situation where: the demand is directed from many demand nodes to a few destination nodes; the network topology consists of hub & spoke trees, dual-hubbed access rings and backbone rings, connected in a hierarchical manner; the transport costs dominate the equipment costs; and the network may consist of several hundred demand nodes.